/*
提交链接：https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/564494001
1552. 两球之间的磁力-中等
完成日期：2024/9/13
二分搜索
*/

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());  // 排序位置
        int left = 1;  // 最小磁力
        int right = position.back() - position.front();  // 最大磁力范围
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canPlace(position, m, mid)) {
                left = mid + 1;  // 如果可以放置，尝试更大的磁力
            } else {
                right = mid - 1;  // 如果不能放置，尝试更小的磁力
            }
        }
        return right;  // 返回最大化的最小磁力
    }
private:
    bool canPlace(const vector<int>& position, int m, int minDist) {
        int count = 1;  // 放置第一个球
        int lastPosition = position[0];  // 记录最后一个球的位置
        
        for (int i = 1; i < position.size(); ++i) {
            if (position[i] - lastPosition >= minDist) {
                ++count;  // 放置新球
                lastPosition = position[i];  // 更新最后一个球的位置
                if (count >= m) {
                    return true;  // 成功放置足够的球
                }
            }
        }
        return false;  // 未能放置足够的球
    }
};